package org.example.leetcode;

/**
 * @author: lynn
 * @Descript: 搜索旋转排序数组
 * @Link: https://www.bilibili.com/video/BV1sK4y1E7tW?from=search&seid=5981301919011380304
 * @date: 2021/8/3 11:09
 * @version: 1.0
 */
public class LC33 {
    public static void main(String[] args) {
        LC33 lc=new LC33();
        int[] arr=new int[]{4,5,6,7,0,1,2};
        int target=7;
        System.out.println(lc.search(arr,target));
    }


    //升序排列
    public int search(int[] nums, int target) {
        if (nums.length==0) return -1;
        if (nums.length==1) return nums[0]==target?0:-1;
        int cutoff=0;
        for (int i=1;i<nums.length;i++) {
            if (nums[i] < nums[i - 1]) {
                cutoff = i - 1;
                break;
            }
        }
        int left=findByTwoSearch(nums,0,cutoff,target);//{4,5,6,7,0,1,2,3}
        int right=findByTwoSearch(nums,cutoff+1,nums.length-1,target);
        return left==-1?right:left;
    }
    public int findByTwoSearch(int[] nums,int start,int end,int target){
        //fixme 二分法写法
        while (start<=end){
            int mid=start+(end-start)/2;
            if (nums[mid]<target){
                start=mid+1;
            }else if (nums[mid]>target){
                end=mid-1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}
